/ >> augmented_containers >> augmented_deque_t
jhcarl0814.github.io
Augmented Containers
Sequence
augmented_*****_t
augmented_********_t
Associative
augmented_***​/​***​/​********​/​********_t
*****
augmented_*****_t
augmented_containers::​augmented_deque_t
template<
typename element_t,
typename allocator_t = std::allocator<element_t>,
typename requested_stride_to_projector_and_accumulator_map_t = std::tuple<>
> struct augmented_deque_t;
augmented_deque_t is an augmented, strictly double-ended queue. It's part of the augmented containers library, providing a stronger version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity).
- An augmented_deque_t has at least one sub-sequences, each having a compile-time or run-time specified stride (if run-time specified, can be adjusted at any time, although does not affect grouping of already enququed elements), an optional projector and an optional accumulator. Container elements are shared between all sub-sequences and are stored in sub-sequence 0. In every subsequence, every neighboring stride elements are projected into a projected result (if stride is compile-time specified and equals to 1, this step can be skipped), then accumulated into an accumulated result (this step can also be skipped if you only need the projected result; on sub-sequences other than sub-sequence 0 whose stride is compile-time specified and equals to 1, it's meaningless to skip both projection and accumulation steps and thus is not allowed).
- augmented_deque_t allows range update: first modify some elements, then call update_range to refresh the projected results and accumulated results that covers those elements in O(distance(range)+(lg(N)-lg(distance(range)))) time (as elements are organized in prefect binary trees, the number of most of the internal nodes to be updated is O(distance(range))). A common mistake would be to forget to call update_range.
- augmented_deque_t allows subrange query: call read_range to collect projected results and accumulated results that covers the range in O(lg(distance(range))) time. If the accumulated result is a range instead of a single value, the result is probably formed by projected results linking to each other, in this case you should not call read_range because there are no more pointers left for you to form another range (see examples below for an intuitive feel).
- augmented_deque_t does not allow inserting or removing elements in the middle. Having this restriction allows it to privide the striding functionality (which the more general augmented_sequence_t can not provide.)
Complexity Table
| possible implementations: |
adding a side deque |
augmented balanced tree |
augmented_deque_t |
| range update |
O(N), O(distance(range)) if range's begin/end is at accumulation end |
O(distance(range)+(lg(N)-lg(distance(range)))) |
O(distance(range)+(lg(N)-lg(distance(range)))) |
| subrange query |
O(distance(range)), O(1) if range's begin/end is at accumulation begin |
O(lg(distance(range))) |
O(lg(distance(range))) |
| enqueue |
O(1) |
O(lg(N)) |
O(1) |
| dequeue |
O(1) |
O(lg(N)) |
O(1) |
| modify element at either end, then update |
O(N), O(1) if at the accumulation end |
O(lg(N)) |
O(1) |
How to achieve O(1) enqueue && O(1) dequeue && O(lg(N)) accumulation depth?
augmented_deque_t is a node-based container. First the element nodes forms a doubly linked list, then tree nodes organize them into prefect binary trees. The enqueue and dequeue operations are analogous to operator++ and operator-- in binary positional numeral system.
- When enqueue operations comes consecutively, the most frequent operation is new tree_node_t whose number is equal to the number of internal nodes in perfect binary trees which is less than the number of elements. (Carrying at position () happens every enqueue operations, so every enqueue operation pays points of energy for each position (O(1) points of energy for all positions in sum).)
- When dequeue operations comes consecutively, the most frequent operation is delete p_tree_node whose number is equal to the number of internal nodes in perfect binary trees which is less than the number of elements.
- When enqueue and dequeue operations comes alternately, in order to prevent cascading carrying and borrowing between numbers like 0b01111111 and 0b10000000, a modified binary positional numeral system which allows each position to be 0, 1 or 2, is used:
... and note that in the implementation it's double ended (the most significant bit is in the middle and shared by the front part and the back part). The accumulation direction is from the middle digit to both ends (the accumulator should be able to accumulate up to 3 (instead of 2) values at a time, e.g. for each digit node on the right, calculate sum of values from its prev digit node, from its left tree root and from its right tree root), then accumulate the ends together yielding the overall accumulated result of the whole container. That's why updating a element at (near) either end and refreshing the accumulated results only takes O(1).
Examples
The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.
In each sub-sequence, the digit nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node's next, middle, prev and accumulated_storage are drawn separately to not break graphviz's layout.
In each digit node's each tree, the tree nodes are organized into a perfect binary tree. The pointer from the root tree node to digit node and pointers from leaf tree nodes to list nodes are 0b1-tagged.
In each sub-sequence, the list nodes are organized into a circular doubly linked list. Pointers from/to the end node are 0b1-tagged. The end node is not drawn to not break graphviz's layout.
empty
The projection and accumulation steps are skipped. What's left can be seen as a std::vector/std::deque that never invalidates iterators/references/pointers, or a std::list with random access ability.
augmented_containers::augmented_deque_t<
char,
std::allocator<char>
> augmented_deque;
accumulator_only_yield_one_value_string
The projection step is skipped. element_t(char)s are accumulated into accumulated_storage_t(std::string)s.
augmented_containers::augmented_deque_t<
char,
std::allocator<char>,
std::tuple<
std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_sequence_t<char, std::string>>
>
>
projector_and_accumulator_yield_one_value_int
sequence 0: the projection step is skipped; accumulator is int operator+(int, int). sequence 1: every 3 element_t(int)s are projected into their std::ranges::max_element, then accumulated into their std::ranges::min.
augmented_containers::augmented_deque_t<
int,
std::allocator<int>,
std::tuple<
std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<int>>,
std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<int>>
>
> augmented_deque;
projector_and_accumulator_yield_one_value_string
sequence 0: the projection step is skipped; accumulator is std::string operator+(std::string const&, std::string const&). sequence 1: every 3 element_t(std::string)s are projected into their std::ranges::max_element, then accumulated into their std::ranges::min.
augmented_containers::augmented_deque_t<
std::string,
std::allocator<std::string>,
std::tuple<
std::pair<std::integral_constant<std::size_t, 1>, augmented_containers::augmented_deque_helpers::example_stride1_chunk1_projector_skipped_and_accumulator_plus_t<std::string>>,
std::pair<std::integral_constant<std::size_t, 3>, augmented_containers::augmented_deque_helpers::example_chunkgt1_projector_max_element_and_accumulator_min_t<std::string>>
>
> augmented_deque;
projector_and_accumulator_yield_multiple_values
sequence 0: the projection and accumulation steps are skipped. sequence 1: every 3 element_t(int)s are projected into their std::ranges::stable_sort (stores addresses so you can modify the original elements), then accumulated into their std::ranges::merge | std::views::take(3) (stores addresses so you can modify the original elements).
augmented_containers::augmented_deque_t<
int,
std::allocator<int>,
std::tuple<
std::pair<std::integral_constant<std::size_t, 3>, projector_and_accumulator_min_n_element_t<int, 3, true>>
>
> augmented_deque;
projector_and_accumulator_yield_one_view
each element_t(int)s is projected into the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.
augmented_containers::augmented_deque_t<
int,
std::allocator<int>,
std::tuple<
std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_diffing_adjacent_element_t>
>
> augmented_deque;
projector_and_accumulator_yield_multiple_views
Similar to the projector_and_accumulator_yield_one_view example, except that each accumulated_storage_t is "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).
augmented_containers::augmented_deque_t<
int,
std::allocator<int>,
std::tuple<
std::pair<std::integral_constant<std::size_t, 1>, projector_and_accumulator_group_by_t>
>
> augmented_deque;
Relationship with <algorithm> and <ranges>
The table shows the constructs that augmented_deque_t provides a stronger replacement of and the constructs that are not relevant and the reasons.
| headers: |
<algorithm> |
<ranges> |
| use projection to handle (without accumulation) |
transform
adjacent_difference |
ranges::transform_view
ranges::elements_view
ranges::keys_view
ranges::values_view
ranges::adjacent_view
ranges::adjacent_transform_view
ranges::slide_view
ranges::chunk_view
ranges::stride_view |
| use accumulation (possibly after projection) to handle |
all_of, any_of, none_of
count
count_if
find
find_first_of
adjacent_find
is_partitioned
partition_point
is_sorted
is_sorted_until
max_element
min_element
minmax_element
accumulate (reduce, transform_reduce) |
ranges::join_view
ranges::join_with_view |
| use accumulation (possibly after projection) + read_range to handle |
partial_sum
exclusive_scan (transform_exclusive_scan)
inclusive_scan (transform_inclusive_scan) |
|
| use yield_multiple_values example to handle |
nth_element (when n is small)
make_heap
push_heap
pop_heap
sort_heap |
|
| use yield_one_view example to handle |
lower_bound (yields one view of iterators, distance > 1 when original sequence is not sorted)
upper_bound (yields one view of iterators, distance > 1 when original sequence not sorted)
equal_ranges (yields one view of ranges, distance > 1 when original sequence not sorted) |
ranges::filter_view
ranges::take_view
ranges::take_while_view
ranges::drop_view
ranges::drop_while_view
ranges::split_view
ranges::chunk_by_view |
| not relevant |
for_each
generate
iota |
ranges::empty_view
ranges::single_view
ranges::iota_view
ranges::basic_istream_view
ranges::repeat_view
ranges::cartesian_product_view
views::all_t
ranges::ref_view
ranges::owning_view
ranges::lazy_split_view
views::counted
ranges::common_view
ranges::reverse_view
ranges::as_const_view
ranges::as_rvalue_view |
| aims at order-of/modifying/reordering elements (checks physical storage style/changes physical storage style/changes sequential relationships between elements, for future use) instead of calculating a result, so not relevant |
copy
move
fill
remove
replace
swap
reverse
rotate
shift_left
shift_right
unique
partition
stable_partition
sort
partial_sort
stable_sort
merge
inplace_merge
is_heap
is_heap_until
is_permutation
next_permutation
prev_permutation |
|
| calculated result can not be reused and must be recalculated every time, so not relevant |
shuffle
sample |
|
| requires domain-specific algorithm, generality is sacrificed, so not relevant |
search |
|
| requires multiple sequences, so not relevant |
mismatch
find_end
starts_with
ends_with
includes
set_difference
set_intersection
set_symmetric_difference
set_union
equal
lexicographical_compare
lexicographical_compare_three_way
inner_product |
ranges::zip_view
ranges::zip_transform_view |